// 文件名：sorted_lookup_table.cpp
// 目的：用排序后的连续容器（std::vector）构建一个只读查找表，
//      通过二分查找（std::lower_bound）以 O(log n) 时间按用户名查找用户 ID。
// 设计要点：
//   - build：接收源数据（按值传入，便于复用调用方容器并在内部排序后整体移动到 records_），
//            以用户名排序，保证可二分查找；
//   - findId：使用异构比较（UserRecord vs std::string_view），避免构造临时 std::string；
//             若找到精确匹配，则返回对应 id，否则返回 std::nullopt；
//   - 数据布局：使用 std::vector<UserRecord>，缓存友好、内存紧凑，对读多写少的场景友好。
// 注意事项：
//   - 若用户名可能重复：lower_bound 返回第一个匹配位置，可按需处理重复（例如选择第一条或报错）；
//     本示例假设用户名唯一（常见系统约束）。
//   - 若需要频繁查找且少量更新：vector + 排序 + 二分通常优于树状结构；若更新频繁，考虑 unordered_map。
//   - 异构比较：比较器形参为 (const UserRecord&, std::string_view)，避免 findId 时分配/拷贝。
//   - 性能提示：构建后表固定不变时，可调用 records_.shrink_to_fit() 减少内存冗余（可选）。

#include <vector>
#include <string>
#include <algorithm>
#include <optional>
#include <iostream>
#include <string_view>
#include <cstdint>

// 用户记录：用户名与其 ID（假设唯一）
struct UserRecord {
    std::string username;
    std::uint32_t id;
};

class UserDirectory {
public:
    // 构建目录：对输入数据按 username 排序后，移动到内部存储
    // 复杂度：O(n log n)
    void build(std::vector<UserRecord> source) {
        std::sort(source.begin(), source.end(),
                  [](const auto& lhs, const auto& rhs) {
                      return lhs.username < rhs.username; // 按字典序升序
                  });
        records_ = std::move(source);
        // 可选：records_.shrink_to_fit(); // 若构建后尺寸固定，收缩容量
    }

    // 按用户名查询 ID（无拷贝查找）
    // 参数：name —— 待查用户名（string_view 避免临时分配）
    // 返回：存在则返回 id，否则返回 std::nullopt
    // 复杂度：O(log n)
    std::optional<std::uint32_t> findId(std::string_view name) const {
        // lower_bound 找到第一个 username >= name 的位置
        auto it = std::lower_bound(
            records_.begin(), records_.end(), name,
            [](const UserRecord& record, std::string_view key) {
                return record.username < key; // 异构比较，减少临时对象
            });

        // 验证是否精确命中（避免仅仅是“下界位置”但不相等的情况）
        if (it != records_.end() && it->username == name) {
            return it->id;
        }
        return std::nullopt;
    }

private:
    // 排序后的只读查找表（读多写少）
    std::vector<UserRecord> records_;
};

int main() {
    UserDirectory directory;

    // 构建时打乱顺序，内部会排序为：alice(1001), bob(1002), charlie(1003)
    directory.build({
        {"alice",   1001},
        {"charlie", 1003},
        {"bob",     1002}
    });

    // 查询示例：命中与未命中
    for (std::string_view query : {"alice", "dave"}) {
        auto id = directory.findId(query);
        if (id) {
            std::cout << "Found " << query << " -> " << *id << '\n';
        } else {
            std::cout << "No record for " << query << '\n';
        }
    }
    return 0;
}